package com.heima.leetcode.practice;

/**
 * @author 勾新杰
 * @version 1.0
 * @description: leetcode 19 删除链表的倒数第 N 个结点
 * @date 2024/12/6 8:36
 */
public class E19 {

    /**
     * <h3>方法一：双指法，固定窗口</h3>
     *
     * @param head 链表的头节点
     * @param n    倒数第 n 个节点
     * @return 删除后的链表头节点
     */
    @SuppressWarnings("all")
    public ListNode removeNthFromEnd1(ListNode head, int n) {
        // 创建哨兵节点（也称为哑节点或虚拟头节点），它的next指向真正的头节点。
        // 这样可以简化一些边界条件的处理，比如当需要删除的是头节点的时候。
        ListNode sentinel = new ListNode(-1);
        sentinel.next = head;

        // 初始化两个指针p1和p2，以及一个前驱节点prev。
        // p1用于定位要删除的节点，p2用于遍历到链表末尾，prev是p1的前一个节点。
        ListNode p1 = head, p2 = head, prev = sentinel;

        // 让p2先向前走n步，这样p1和p2之间就相隔了n个节点。最后的情况是p2会指向null，所以p1是指定要删除节点，p2是null
        for (int i = 0; i < n; i++) {
            p2 = p2.next;
        }

        // 同时移动p1和p2，直到p2到达链表末尾。
        // 此时p1正好指向要删除的节点。
        while (p2 != null) {
            prev = p1;
            p1 = p1.next;
            p2 = p2.next;
        }

        // 修改prev的next指针跳过p1，从而移除了p1指向的节点。
        prev.next = p1.next;

        // 返回新的头节点，即哨兵节点的下一个节点。
        return sentinel.next;
    }

    /**
     * 记录当前是倒数的第几个节点
     */
    private int count = 0;

    /**
     * <h3>方法二：递归法</h3>
     *
     * @param head 链表的头节点
     * @param n    倒数第 n 个节点
     * @return 删除后的链表头节点
     */
    public ListNode removeNthFromEnd2(ListNode head, int n) {
        if (head.next == null) {
            if (++count == n) return null;
            else return head;
        }
        ListNode next = removeNthFromEnd2(head.next, n);
        if (++count == n) return head.next;
        else {
            head.next = next;
            return head;
        }
    }
}
